#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        sort(rewardValues.begin(), rewardValues.end());
        int n = rewardValues.back();
        vector<int> dp(2 * n);
        dp[0] = 1;
        for (auto x : rewardValues) {
            for (int i = 2 * x - 1; i >= x; i--) {
                if (dp[i - x]) dp[i] = 1;
            }
        }
        int ret = 0;
        for (int i = 0; i < dp.size(); i++) if (dp[i]) ret = i;
        return ret;
    }
};